package com.cat.enumerate;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/powerful-integers/?envType=problem-list-v2&envId=enumeration
 * @create 2025/9/20 20:18
 * @since JDK17
 */

public class Solution05 {
    int bound;

    void add(int x, Set<Integer> list) {
        if (x == 1) {
            list.add(1);
        } else {
            for (int i = 1; i <= bound; i *= x) {
                list.add(i);
            }
        }
    }

    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        List<Integer> ans = new ArrayList<>();
        Set<Integer> xl = new HashSet<>(), yl = new HashSet<>();
        this.bound = bound;
        add(x, xl);
        add(y, yl);
        int n = xl.size(), m = yl.size();
        for (int i = 1; i <= bound; i++) {
            for (Integer num : xl) {
                if (yl.contains(i - num)) {
                    ans.add(i);
                    break;
                }
            }
        }
        return ans;
    }
}
